package sort;

import java.util.Random;

public class Sort {

    //冒泡排序
    private static void swap(int[] array,int j,int k) {
        int tmp = array[j];
        array[j] = array[k];
        array[k] = tmp;
    }
    public static void bubbleSort(int[] array){  //冒泡排序
        //有n个数,则需要进行n - 1次排序.
        for(int i = 0;i < array.length - 1;i++) {
            for(int j = 0;j < array.length - i - 1;j++){
                if(array[j] > array[j + 1]){
                    swap(array,j,j + 1);
                }
            }
        }
    }

    //选择排序:外层循环就是控制循环次数
    public static void selectSort(int[] array) {
        //首先遍历找出最大值的的下标进行记录
        for(int i = 0;i < array.length - 1;i++){   //本次循环最终仍然表示的要交换的次数
            int maxIndex = 0;   //假设最大值的下标就是0
            for(int j = 0;j < array.length - i;j++){    //遍历除去最大值之后的循环次数
                if(array[j] > array[maxIndex]){  //判断值是否比最大值要大,进行更新下标
                    maxIndex = j;
                }
            }
            //找到最大值得下标,进行交换
            swap(array,maxIndex,array.length - i - 1);
        }
    }
    //选出最小的数放前面
    public static void selectSort1(int[] array) {
        int len = array.length;
        for(int i = 0;i < len - 1;i++){
            int minIndex = i;
            for(int j = i;j < len;j++){
                if(array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    //插入排序
    public static void insertSort(int[] array) {
        //将无序区间的值放入到有序区间当中
        for(int i = 0;i < array.length - 1;i++){
            //默认刚开始就是有序区间
            int tmp = array[i + 1];
            int j;
            for(j = i;j >= 0;j--) {        //在无序区间的第一个值与有序区间进行比较
                if(tmp > array[j]){        //在原本有序的区间中比较的是无序区间的值
                    break;
                }
                array[j + 1] = array[j];
            }
            array[j + 1] = tmp;  //将搬移后的前一个位置改为无序区间的第一个值
        }
    }


    ///希尔排序:先按照一定的间隔进行插入排序
    //时间复杂度O(n^1.3~1.4)  不具备稳定性
    public static void shellSort(int[] array) {
        int gap = array.length / 2;
        while(gap > 1){
            insertSortWithGap(array,gap);
            gap = gap/2;
        }
        //循环结束后再进行一次插排
        insertSortWithGap(array,1);
    }
    public static void insertSortWithGap(int[] array,int gap) {
        //所要比较次数就是length - gap;
        for(int i = 0;i < array.length - gap;i++){
            int k = array[gap + i]; //记录后一组的同等位置元素
            int j;
            for(j = i;j >= 0 && k < array[j];j-=gap) {
                array[j + gap] = array[j];
            }
            array[j + gap] = k;
        }
    }


    //堆排序
    public static void shiftDown(int[] array,int index,int size){
        while(2 * index + 1 < size){  //如果左子树没有那怎么直接结束
            int max = 2 * index + 1;
            int right = 2 * index + 2;
            if(right < size && array[right] > array[max]){
                max = right;
            }
            if(array[max] < array[index]){
                return;
            }
            swap(array,max,index);
            index = max;
        }
    }
    public static void creatHeap(int[] array){
        for(int i = (array.length - 1);i > 0;i--){
            shiftDown(array,i,array.length);   //向下调整建堆
        }
    }
    public static void heapSort(int[] array){
        //创建大堆
        creatHeap(array);
        for(int i = 0;i < array.length - 1;i++){ //确定交换次数
            //确定无序区间[array.length,size)
            swap(array,0,array.length - i - 1);
            shiftDown(array,0,array.length - i - 1);
        }
    }



    public static int partition(int[] array,int from,int to) {
        //记录pivot的值
        int pivot = array[to];  //区间分割点
        int left = from;
        int right = to;
        //[from,left)都是<=pivot的值;  [right,to]的值都是大于pivot的值
        while(left < right) {
            //if(array[left] <= pivot) left++;
            //if(array[right] > pivot) right++;
            while(left < right && array[left] <= pivot){
                left++;
            }
            while (left < right && array[right] >= pivot) {
                right--;
            }
            //left right出循环后left值大于pivot,right值小于pivot
            swap(array,left,right);
        }
        //循环结束后必定left == right; 交换left与pivot的值
        swap(array,left,to);
        return left;  //返回目前pivot所在的下标
    }
    /*
    挖坑法
    减少了赋值次数,数据量大时节省了大量时间
     */
    public static int partition1(int[] array,int from,int to) {
        int pivot = array[to];
        int left = from;
        int right = to;
        while(left < right) {
            while(left < right && array[left] <= pivot){
                left++;
            }
            array[right] = array[left];  //左边卡住时,将左边的值赋值给右边,再从右边开始循环
            while(left < right && array[right] >= pivot){
                right--;
            }
            array[left] = array[right];  //右边卡主是,将右边的值赋值给左边,循环再从左边开始
        }
        array[left] = pivot;
        return left;
    }

    /**使用下标index保证[from,index)位置全部都是小于pivot的值
     *执行结束时index位置的值一定是大于或者等于pivot的值,此时将pivot的值与index进行交换,返回index下标
     * @param array
     * @param from 开始位置
     * @param to   结束位置
     * @return index:pivot所在的下标
     */
    public static int partition2(int[] array,int from,int to) {
        int pivot = array[to];
        int index = from; //定义下标index让[from,index)范围内全部都是<pivot的值
        for (int i = from; i < to; i++) {
            if (array[i] < pivot) {
                swap(array, i, index);
                index++;
            }
        }
        //循环结束后返回pivot的下标
        swap(array, index, to);
        return index;
    }
    //快速排序
    public static void quickSort(int[] array) {
        sortRange(array,0,array.length - 1);
    }
    public static void sortRange(int[] array,int from,int to){
        //采用递归
        if(from >= to) {
            return;
        }
        int[] indices = partitionPlus(array,from,to);
        int less = indices[0];
        int great = indices[1];
        sortRange(array,from,less);
        sortRange(array,great,to);
//        int pi = partition2(array,from,to);
//        //处理pivot左边区间
//        sortRange(array,from,pi - 1);
//        //处理右边区间
//        sortRange(array,pi + 1,to);
    }
    public static int[] partitionPlus(int[] array,int from,int to) {
        Random random = new Random();
        int index = random.nextInt(to - from) + from;
        int left = from;
        int right = to;
        int pivot = array[index];
        int i = left;
        while(i <= right){
            if(array[i] < pivot) {
                swap(array,i,left);
                left++;
                i++;
            }else if(array[i] > pivot) {
                swap(array,i,right);
                right--;
            }else{
                i++;
            }
        }
        return new int[]{left - 1,right + 1};
    }

    public static void main(String[] args) {
        Random random = new Random();
        int a = random.nextInt(3);
        System.out.println(a);
    }
}
